package algorithm;

import java.util.ArrayList;
import java.util.LinkedList;

public class QuadtreeFreeman {

	private int[] deplX={-1,-1,0,1,1,1,0,-1};	// les d�placements par rapport � l'axe des X
	private int[] deplY={0,1,1,1,0,-1,-1,-1};
	private int[][] image={{0,0,0,0,0},{0,1,1,0,0},{0,0,1,1,0},{0,0,0,1,0},{0,0,0,0,0}};

	public QuadtreeFreeman(int[][] image){
		this.image=image;
	}

	public ArrayList<Integer> coding() {
		ArrayList<Integer> codage = new ArrayList<Integer>();
		int[] chiffres = new int[8];
		for(int k=0;k<chiffres.length;k++){
			chiffres[k]=0;
		}
		LinkedList<int[][]> imageDecoupe = this.division(image, 0);
		for(int[][] tableau : imageDecoupe){
			for(int i=1;i<tableau.length-1;i++){
				for(int j=1;j<tableau[0].length-1;j++){
					if(tableau[i][j] != 0){
						for(int k=0;k<chiffres.length;k++){
							if(tableau[i+deplX[k]][j+deplY[k]] != 0){
								chiffres[k]++;
							}
						}
					}
				}
			}
			for(int k=0;k<chiffres.length;k++){
				codage.add(chiffres[k]);
				chiffres[k]=0;
			}
		}
		/*System.out.println("Codage :");
		for(int a : codage){
			System.out.print(a);
		}
		System.out.println();*/
		return codage;
	}

	private LinkedList<int[][]> division(int[][] image, int profondeur) {
		LinkedList<int[][]> listeImages = new LinkedList<int[][]>();
		if(profondeur == 0){
			int[][] imageContour = new int[image.length+2][image[0].length+2];
			for(int i=0;i<imageContour.length;i++){
				for(int j=0;j<imageContour[0].length;j++){
					if(i == 0 || j == 0 || i == imageContour.length-1 || j == imageContour[0].length -1){
						imageContour[i][j] = 0; // On ajoute un contour blanc pour simplifier les calculs suivants
					}
					else{
						imageContour[i][j] = image[i-1][j-1];
					}
				}
			}
			listeImages.add(imageContour);
			return listeImages;
		}
		else{
			int[][] hautGauche = new int[image.length/2][image[0].length/2];
			int[][] hautDroite = new int[image.length/2][image[0].length-(image[0].length/2)];
			int[][] basGauche = new int[image.length-(image.length/2)][image[0].length/2];
			int[][] basDroite = new int[image.length-(image.length/2)][image[0].length-(image[0].length/2)];
			for(int i=0;i < image.length;i++){
				for(int j=0;j < image[0].length;j++){
					if(i<(image.length/2)){
						if(j<(image[0].length/2)){
							hautGauche[i][j] = image[i][j];
						}
						else{
							hautDroite[i][j%(image[0].length/2)] = image[i][j];
						}
					}
					else{
						if(j<(image[0].length/2)){
							basGauche[i%(image.length/2)][j] = image[i][j];
						}
						else{
							basDroite[i%(image.length/2)][j%(image[0].length/2)] = image[i][j];
						}
					}
				}
			}
			listeImages.addAll(division(hautGauche, profondeur-1));
			listeImages.addAll(division(hautDroite, profondeur-1));
			listeImages.addAll(division(basGauche, profondeur-1));
			listeImages.addAll(division(basDroite, profondeur-1));
			return listeImages;
		}
	}
}
